class Solution:
    def longestIncreasingPath(self, matrix: list) -> int:
        if not matrix:
            return 0
        self.length, self.height = len(matrix[0]), len(matrix)
        res = [0]
        self.matrix = matrix
        self.searched_matrix = [[0] * self.length for i in range(self.height)]
        for i in range(self.height):
            for j in range(self.length):
                res.append(self.search(i, j))
        return max(res)

    def search(self, i, j):
        if self.searched_matrix[i][j] != 0:
            return self.searched_matrix[i][j]
        num = self.matrix[i][j]
        top = self.search(i - 1, j) if i > 0 and self.matrix[i - 1][j] > num else 0
        left = self.search(i, j - 1) if j > 0 and self.matrix[i][j - 1] > num else 0
        botton = self.search(i + 1, j) if i < self.height - 1 and self.matrix[i + 1][j] > num else 0
        right = self.search(i, j + 1) if j < self.length - 1 and self.matrix[i][j + 1] > num else 0
        max_deepth = max(top, left, botton, right) + 1
        self.searched_matrix[i][j] = max_deepth
        return max_deepth


a = Solution()
print(a.longestIncreasingPath([[9, 9, 4],
                               [6, 6, 8],
                               [2, 1, 1]]))
print(a.longestIncreasingPath([]))
print(a.longestIncreasingPath([[]]))
print(a.longestIncreasingPath([[1]]))
